function TreeCode() {
    let TreeNode = function (value) {
        this.val = value;
        this.left = null;
        this.right = null;
    }

    this.createTree = function () {
        let biTree = new TreeNode('1');
        biTree.left = new TreeNode('2');
        biTree.right = new TreeNode('3');
        biTree.left.left = new TreeNode('4');
        biTree.left.right = new TreeNode('5');
        biTree.right.left = new TreeNode('6');
        biTree.right.right = new TreeNode('7');
        biTree.right.right.left = new TreeNode('8');
        return biTree;
    }
}

/**
 * 数据结构：队列
 */
function Queue() {
    var data = []
    var front = 0
    var rear = 0
    // 出列
    this.pop = function () {
        if (front === rear) {
            return null
        }
        return data[front++]
    }
    // 入列
    this.push = function (value) {
        data[rear++] = value
    }
}

function NLR(root) {
    if (root == null) {
        return
    }
    console.log(root.val)
    NLR(root.left)
    NLR(root.right)
}

function LNR(root) {
    if (root == null) {
        return
    }
    LNR(root.left)
    console.log(root.val)
    LNR(root.right)
}

function LRN(root) {
    if (root == null) {
        return
    }
    LRN(root.left)
    LRN(root.right)
    console.log(root.val)
}

function levelTraversal(root) {
    if (root == null) {
        return
    }
    console.log(root.val)
    if (root.left !== null) {
        queue.push(root.left)
    }
    if (root.right !== null) {
        queue.push(root.right)
    }
    levelTraversal(queue.pop())
}

var queue = new Queue()
var tree = new TreeCode();
console.log('---------前序遍历--------')
NLR(tree.createTree())
console.log('---------中序遍历--------')
LNR(tree.createTree())
console.log('---------后序遍历--------')
LRN(tree.createTree())
console.log('---------层序遍历--------')
levelTraversal(tree.createTree())
